People regularly tell me that imperative programming is the natural form of programming because 'people think imperatively'. I can see where they are coming from. Why, just the other day I found myself saying, "Hey Chris, I'm hungry. I need you to walk into the kitchen, open the cupboard, take out a bag of bread, open the bag, remove a slice of bread, place it on a plate..." Unfortunately, I hadn't specified where to find the plate so at this point Chris threw a null pointer exception and died.
The truth is that people think in a variety of different ways in different situations. Most people resort to detailed imperative instructions only when describing complicated or unfamiliar tasks (or when explaining how to interact with a machine, which is itself indicative of how pervasive this mindset is in programming). Even then, the resulting communication is unlikely to resemble a perfectly sequential program and will be full of ambiguity, missing steps and contextual assumptions. Anyone who has ever tried to assemble Ikea furniture knows that clearly communicating or precisely following a series of instructions is actually quite difficult. Indeed, one of the hardest things that beginner programmers have to learn is how to break down a task into a series of simple instructions with no ambiguity. It takes years of practice before the process becomes natural, and meanwhile programming courses have a high failure rate.
If we are going to base the design of our tools on poorly thought-out metaphorical comparisons to making lunch then let's at least be realistic about it. 'Make me a ham sandwich, there is bread in the cupboard' will indeed cause Chris to look in the cupboard. But if there is in fact no bread there, instead of exploding he will probably look elsewhere or ask for clarification. Rather than providing detailed instructions, I provide a goal (sandwich) and hints on how to execute it (try looking for bread in the cupboard). Further constraints are inferred from context and general knowledge (the sandwich should be less than one foot long, there should not be mayo all over the counter afterwards). Chris calculates a series of actions that will produce the desired result and modifies that plan as new information and constraints come to light (no bread in the cupboard).
The reason for communicating in this way is that I don't care exactly how the sandwich is made, so long as it is done neatly and quickly. Communicating my exact intent makes the resulting 'program' simpler and more flexible. I may give additional hints and restrictions when they necessary to speed up the process and Chris may ask for clarification if at any point he is unable to plan a path to the goal, but I never have to resort to a full imperative description of the problem.
Today's computers don't have enough contextual knowledge to make me a sandwich but there are lots of domains where this approach excels. The classic example is SQL databases. Rather than specifying exact data-structures and operations, the user specifies a high-level schema and sends descriptions of queries. It is the responsibility of the database to choose storage types, manage concurrent changes and generate query plans. It makes these decisions based on cost models, runtime information and constrained search (e.g., postgres uses a genetic search algorithm to choose efficient plans for large queries). If the database makes bad decisions, the user can help it out by adding size hints, specifying indexes and overriding query plans. So long as the process of turning intent into plans is transparent and interactive there is no need to invoke a sufficiently smart compiler. A dumb compiler can do the easy but tedious legwork and the human can supervise and correct mistakes. This saves programmer time, makes the intent of the resulting program easier to understand (because it is not cluttered with irrelevant details) and makes it easier to change parts of the system independently (eg adding an index does not require rewriting all of your queries). There is a reason why SQL databases became a standard storage mechanism - this model of programming works incredibly well in this domain.
Indeed, the most painful part of using an SQL database is the interface back to purely imperative programming. The Object-Relational mismatch is often seen as a failure of SQL databases. But consider the relative strengths and learning curves of the two technologies. SQL is often still used for its original goal: enabling non-programmers to mine data. The database handles choice of serialization protocol, data structures for storage and indexing, query algorithms and manages concurrency. For the majority of applications it makes good enough decisions that the user never needs to provide any hints beyond index choice. Imperative programming, on the other hand, requires the user to handle all of these decisions and requires years of practice before the user can reliably build the same kinds of applications. In that light, it is interesting that the popular trend is towards making databases more like imperative languages (NoSQL, object databases) rather than making programming look more like SQL.
To be clear, SQL is a mess. I claim that it is successful despite its many flaws because of the power of the core ideas:
- separate goals from plans
- separate logical data models from physical data-structures
- automatically handle the translation from goals to plans and from logical to physical models
- make the translation transparent and allow the user to provide hints or override sections
These ideas allow the programming environment to capture the correct level of detail ('make me a sandwich' rather than 'go to the kitchen, open the cupboard...'). This separates meaning from optimisation giving both the user and the compiler more leeway to change the operational details of the program without modifying the specification. The transparency allows us to build this without requiring a SufficientlySmartCompiler™.
This model is well understood in the database world and is the subject of decades of research. Unfortunately the database world and the programming language world rarely interact and so the results are mostly confined to data management systems and rarely extend to general purpose programming, with the possible exception of the recent revival of the datalog family.
So what would a general purpose language look like if it took these ideas to heart?